package com.thoughtworks.recruit.test.jgraph.graph.operations;

import com.thoughtworks.recruit.test.jgraph.graph.*;
import com.thoughtworks.recruit.test.util.*;
import java.util.*;

/**
 * Fast implementation of DiOperations. This class uses additional data structures to improve
 * the performance of methods which depend on edge retrievals, e.g. getEdge(V u, V v),
 * containsEdge(V u, V v),addEdge(V u, V v). A disadvantage is an increase in memory consumption. If
 * memory utilization is an issue, use a {@link DiOperations} instead.
 *
 * @param <V> the graph vertex type
 * @param <E> the graph edge type
 *
 */
public class FastLookupDiOperations<V, E>
    extends DiOperations<V, E>
{
    private static final long serialVersionUID = 1L;

    /*
     * Maps a pair of vertices <u,v> to a set of edges {(u,v)}. In case of a multigraph, all edges
     * which touch both u,v are included in the set
     */
    protected Map<PairUtil<V, V>, ArraySetUtil<E>> touchingVerticesToEdgeMap;

    /**
     * Construct a new fast lookup directed operations.
     * 
     * @param abstractBaseGraph the graph for which these operations are for
     */
    public FastLookupDiOperations(AbstractBaseGraph<V, E> abstractBaseGraph)
    {
        this(abstractBaseGraph, new LinkedHashMap<>(), new ArraySetEdgeSetFactory<>());
    }

    /**
     * Construct a new fast lookup directed operations.
     * 
     * @param abstractBaseGraph the graph for which these operations are for
     * @param vertexMap map for the storage of vertex edge sets
     */
    public FastLookupDiOperations(
            AbstractBaseGraph<V, E> abstractBaseGraph, Map<V, DiEdgeContainer<V, E>> vertexMap)
    {
        this(abstractBaseGraph, vertexMap, new ArraySetEdgeSetFactory<>());
    }

    /**
     * Construct a new fast lookup directed operations.
     * 
     * @param abstractBaseGraph the graph for which these operations are for
     * @param vertexMap map for the storage of vertex edge sets
     * @param edgeSetFactory factory for the creation of vertex edge sets
     */
    public FastLookupDiOperations(
            AbstractBaseGraph<V, E> abstractBaseGraph, Map<V, DiEdgeContainer<V, E>> vertexMap,
            EdgeSetFactory<V, E> edgeSetFactory)
    {
        super(abstractBaseGraph, vertexMap, edgeSetFactory);
        this.touchingVerticesToEdgeMap = new HashMap<>();
    }

    /**
     * {@inheritDoc}
     */
    @Override
    public Set<E> getAllEdges(V sourceVertex, V targetVertex)
    {
        if (abstractBaseGraph.containsVertex(sourceVertex)
            && abstractBaseGraph.containsVertex(targetVertex))
        {
            Set<E> edges = touchingVerticesToEdgeMap.get(new PairUtil<>(sourceVertex, targetVertex));
            return edges == null ? Collections.emptySet() : new ArraySetUtil<>(edges);
        } else {
            return null;
        }
    }

    /**
     * {@inheritDoc}
     */
    @Override
    public E getEdge(V sourceVertex, V targetVertex)
    {
        List<E> edges = touchingVerticesToEdgeMap.get(new PairUtil<>(sourceVertex, targetVertex));
        if (edges == null || edges.isEmpty())
            return null;
        else
            return edges.get(0);
    }

    /**
     * {@inheritDoc}
     */
    @Override
    public void addEdgeToTouchingVertices(E e)
    {
        V source = abstractBaseGraph.getEdgeSource(e);
        V target = abstractBaseGraph.getEdgeTarget(e);

        getEdgeContainer(source).addOutgoingEdge(e);
        getEdgeContainer(target).addIncomingEdge(e);

        PairUtil<V, V> vertexPairUtil = new PairUtil<>(source, target);
        if (!touchingVerticesToEdgeMap.containsKey(vertexPairUtil)) {
            ArraySetUtil<E> edgeSet = new ArraySetUtil<>();
            edgeSet.add(e);
            touchingVerticesToEdgeMap.put(vertexPairUtil, edgeSet);
        } else
            touchingVerticesToEdgeMap.get(vertexPairUtil).add(e);
    }

    /**
     * {@inheritDoc}
     */
    @Override
    public void removeEdgeFromTouchingVertices(E e)
    {
        V source = abstractBaseGraph.getEdgeSource(e);
        V target = abstractBaseGraph.getEdgeTarget(e);

        getEdgeContainer(source).removeOutgoingEdge(e);
        getEdgeContainer(target).removeIncomingEdge(e);

        // Remove the edge from the touchingVerticesToEdgeMap. If there are no more remaining edges
        // for a pair
        // of touching vertices, remove the pair from the map.
        PairUtil<V, V> vertexPairUtil = new PairUtil<>(source, target);
        if (touchingVerticesToEdgeMap.containsKey(vertexPairUtil)) {
            ArraySetUtil<E> edgeSet = touchingVerticesToEdgeMap.get(vertexPairUtil);
            edgeSet.remove(e);
            if (edgeSet.isEmpty())
                touchingVerticesToEdgeMap.remove(vertexPairUtil);
        }
    }
}